#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD = 1e9+7;
const int MAXN = 1e6+7;
LL FastPOW(LL a, LL k) {
    a %= MOD;
    LL ret = 1;
    while (k) {
        if (k&1) {
            ret = (ret * a) % MOD;
        }
        k = (k >> 1);
        a = (a * a) % MOD;
    }
    return ret;
}
LL F[MAXN];


int main() {
    int T;
    cin>>T;
    LL n, k;
    while (T--) {
        scanf("%lld %lld", &n, &k);
        LL p = FastPOW(2, k);
        F[1] = p; F[2] = p * (p - 1) % MOD;
        for (int i=3; i<=n; ++i) {
            LL& t = F[i];
            LL fi = F[i-2];
            t = (p-1) * fi % MOD + (p*FastPOW(p-1, i-2) % MOD - fi) * (p-2) % MOD;
            t %= MOD;
            if (t < 0) t += MOD;
        }
//        for (int i=1; i<=n; ++i) {
//            printf("%d: %lld\n", i, F[i]);
//        }
//        printf("\n");
        printf("%lld\n", F[n]);
    }
    return 0;
}
